package com.ufpb.algoritmosEstrutura.arvoreGeradoraMinima;

public class Sort {

	public static void quickSort(Rua [] array, int inicio, int fim){
		if(inicio < fim){
			int pivor = particao( array, inicio, fim);
			quickSort(array, inicio, pivor-1);
			quickSort(array, pivor, fim);
		}
	}

	private static int particao(Rua[] array, int inicio, int fim) {
		int pivor = array[fim].getCusto();
		int i = inicio -1;
		for(int j = inicio; j <= fim-1; j++){
			if(array[j].getCusto()<= pivor){
				i+= 1;
				Rua t = array[i];
				array[i]= array[j];
				array[j] = t;
			}
		}
		Rua f = array[i+1];
		array[i+1] = array[fim];
		array[fim] = f;
		return i+1;
	}
	
}
